import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Solution912 {
    /**
     * 给你一个整数数组 nums，请你将该数组升序排列。
     * 示例 1：
     * <p>
     * 输入：nums = [5,2,3,1]
     * 输出：[1,2,3,5]
     * 示例 2：
     * <p>
     * 输入：nums = [5,1,1,2,0,0]
     * 输出：[0,0,1,1,2,5]
     */
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }
        partition(nums, 0, nums.length - 1);
        return nums;
    }

    public void partition(int[] nums, int start, int end) {
        if (start >= end) return;
        int idx = (int) (start + Math.random() * (end - start + 1));
        swap(nums, idx, end);
        int left = start, small = start - 1, large = end;
        while (left < large) {
            if (nums[left] > nums[end]) {
                large--;
                swap(nums, left, large);
                left--;
            } else if (nums[left] < nums[end]) {
                small++;
                swap(nums, left, small);
            }
            left++;
        }
        swap(nums, left, end);
        partition(nums, start, small);
        partition(nums, large + 1, end);
    }

    public void swap(int[] nums, int idx1, int idx2) {
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }

    public static void main(String[] args) {
        Solution912 test = new Solution912();
        System.out.println(Arrays.toString(test.sortArray(new int[]{5, 2, 3, 1})));
    }
}
